package com.practice.niuke.new_direct_practice.class12;

import java.util.HashMap;

/**
 * 一种消息接收并打印的结构设计 已知一个消息流会不断地吐出整数 1~N，
 * 但不一定按照顺序吐出。如果上次打印的数 为 i， 那么当 i+1 出现时，
 * 请打印 i+1 及其之后接收过的并且连续的所有数，直 到 1~N 全部接收 并打印完，
 * 请设计这种接收并打印的结构。初始时默认i==0
 */
public class Code01_ReceiveAndPrintOrderLine {

	public static class Node {
		public String info;
		public Node next;

		public Node(String str) {
			info = str;
		}
	}

	public static class MessageBox {
		private HashMap<Integer, Node> headMap;
		private HashMap<Integer, Node> tailMap;
		private int waitPoint;

		public MessageBox() {
			headMap = new HashMap<Integer, Node>();
			tailMap = new HashMap<Integer, Node>();
			waitPoint = 1;
		}

		/**
		 * 一种消息的接收并打印的结构设计（消息编号一定从1开始）
		 *
		 * @param num 消息的编号
		 * @param info info消息的内容
		 */
		public void receive(int num, String info) {
			if (num < 1) {
				// 无效消息直接返回
				return;
			}
			// 由消息生成节点Node, 在这里Node里面只放消息，不放当前的编号num
			Node cur = new Node(info);
			// （1）在开头map（headMap）和结尾map（tailMap）中生成当前编号num ~ 当前编号num的连续区间: [num, num]
			headMap.put(num, cur);
			tailMap.put(num, cur);
			// 建立了num~num这个连续区间的头和尾后，
			// （2）在结尾map（tailMap）中查询有没有某个连续区间以编号为num-1结尾
			if (tailMap.containsKey(num - 1)) {
				// 如果在结尾map（tailMap）中存在以（num-1）编号节点结尾的连续区间，
				// （2.1）在结尾map中取出这个节点，并且将这个节点的next指针指向当前的节点
				tailMap.get(num - 1).next = cur;
				// （2.2）在结尾map中移除（num-1）为编号的节点
				tailMap.remove(num - 1);
				// （2.3）在开头map中移除以num为编号的节点
				headMap.remove(num);
			}
			// （3）在开头map（headMap）中查询有没有某个连续区间以（num+1）编号节点开头
			if (headMap.containsKey(num + 1)) {
				// 如果在开头map（headMap）中存在以（num+1）编号节点开头的连续区间，
				// （3.1）在开头map中取出这个节点，并且将当前节点的next指针指向这个节点
				cur.next = headMap.get(num + 1);
				// （3.2）在结尾map中移除编号的num的节点
				tailMap.remove(num);
				// （3.3）在开头map中移除编号为（num+1）的节点
				headMap.remove(num + 1);
			}
			if (num == waitPoint) {
				// （4）如果当前节点的编号刚好为waitPoint，在进行完上述操作后，直接打印
				print();
			}
		}

		private void print() {
			Node node = headMap.get(waitPoint);
			headMap.remove(waitPoint);
			while (node != null) {
				System.out.print(node.info + " ");
				node = node.next;
				waitPoint++;
			}
			tailMap.remove(waitPoint-1);
			System.out.println();
		}

	}

	public static void main(String[] args) {
		// MessageBox only receive 1~N
		MessageBox box = new MessageBox();

		box.receive(2,"B"); // - 2"
		box.receive(1,"A"); // 1 2 -> print, trigger is 1

		box.receive(4,"D"); // - 4
		box.receive(5,"E"); // - 4 5
		box.receive(7,"G"); // - 4 5 - 7
		box.receive(8,"H"); // - 4 5 - 7 8
		box.receive(6,"F"); // - 4 5 6 7 8
		box.receive(3,"C"); // 3 4 5 6 7 8 -> print, trigger is 3

		box.receive(9,"I"); // 9 -> print, trigger is 9

		box.receive(10,"J"); // 10 -> print, trigger is 10

		box.receive(12,"L"); // - 12
		box.receive(13,"M"); // - 12 13
		box.receive(11,"K"); // 11 12 13 -> print, trigger is 11

	}
}
